package com.company.algo.SearchAlgorithm.BT;

/**
 * 最小路径和
 * https://leetcode-cn.com/problems/minimum-path-sum/solution/
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 【说明：每次只能向下或者向右移动一步。】

 */
public class MinPathSum {
    int ret = 100 * 200 * 200;
    int[] dx = {0, 1};
    int[] dy = {1, 0};
    boolean[][] visited;
    public int minPathSum(int[][] grid) {
        visited = new boolean[grid.length][grid[0].length];
        visited[0][0] = true;
        dfs(0, 0, grid.length-1, grid[0].length-1,grid[0][0],grid);
        return ret;
    }

    void dfs(int x, int y, int p, int q, int cur, int[][] grid){
        if(x==p && y ==q){
            ret = Math.min(ret,cur);
            return;
        }
        for(int i = 0; i < 2; i++){
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if (nextX >= 0 && nextX < grid.length && nextY >= 0 && nextY < grid[0].length && !visited[nextX][nextY]){
                visited[nextX][nextY] = true;
                cur += grid[nextX][nextY];
                dfs(nextX, nextY, p, q, cur, grid);
                cur -= grid[nextX][nextY];
                visited[nextX][nextY] = false;
            }
        }
    }

    /*前面用回溯会超时，观察到每个节点的状态由其上面和左边的节点决定，所以考虑用动态规划
    * 1.dp[i][j]表示从起点到(i,j)的最小路径和, dp[0][0] = grid[0][0]
    * 2.状态转移需要考虑三种情况，i==0 , j=0 , 其他case
    * 对于i==0 ，dp[i][j] = dp[i][j-1]
    * 对于j=0， dp[i][j] = dp[i-1][j];
    * 其他情况，dp[i][j] = min(dp[i-1][j],dp[i][j-1])
    * */
    public int minPathSum2(int[][] grid) {
       //可以直接使用grid来记录状态变化情况，节省O(N)的空间复杂度
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i==0 && j==0) continue;
                else if (i==0){
                    grid[i][j] += grid[i][j-1];
                }else if (j==0){
                    grid[i][j] += grid[i-1][j];
                }else{
                    grid[i][j] += Math.min(grid[i][j-1],grid[i-1][j]);
                }
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }


}
